package main

/*
	滑动窗口最大值
给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回滑动窗口中的最大值。


示例 1：
输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
输出：[3,3,5,5,6,7]
 */

func maxSlidingWindow(nums []int, k int) []int {
	if k == 1 {
		return nums
	}
	queue := []int{0}
	var results []int

	for i := 1; i < len(nums); i++ {
		// 如果当前位置i与队首位置的长度等于k，
		//则说明队列中的元素覆盖了滑动窗口允许的最大范围，需要弹出队首
		for i-queue[0] >= k {
			queue = queue[1:]
		}

		// 如果队尾对应的值不比待插入的值大，则一直弹出
		for len(queue) > 0 && nums[i] >= nums[queue[len(queue)-1]] {
			queue = queue[:len(queue)-1]
		}
		queue = append(queue, i)

		if i >= k-1 {
			results = append(results, nums[queue[0]])
		}
	}
	return results
}

func main() {
	
}
